#include "BloqueBSharp.h"
#include "Excepciones.h"
#include "DatoBSharp.h"
#include "Registro.h"
#include <list>
#include <algorithm>
#include "funciones.h"

#include <iostream>

namespace Toolkit {

BloqueBSharp::BloqueBSharp(const unsigned long int &tamanoBloque,
		const TipoSerializacion& tSerializacion) :
	Bloque(tamanoBloque, tSerializacion) {
	this->direccion = 0;
	this->nivelNodo = 0;
}

BloqueBSharp::~BloqueBSharp() {
}

unsigned long int BloqueBSharp::getNivelNodo() const {
	return this->nivelNodo;
}

void BloqueBSharp::setNivelNodo(const unsigned long & nivelNodo) {
	this->nivelNodo = nivelNodo;
}

Componente* BloqueBSharp::buscar(const Clave &clave) {
	list<Componente*>::iterator it = componentes.begin();

	while (it != componentes.end()) {
		DatoBSharp *dato = ((DatoBSharp *) ((Registro*) (*it))->clonarDato());
		if ((*dato ->getClave()) == clave) {
			delete dato;
			return *it;
		}

		delete dato;
		it++;
	}

	return NULL;
}

void BloqueBSharp::agregar(Componente *componente, const Clave& clave) {
	//agrega sin chequear maximo y comparando clave/clave, en vez de componente/clave
	//siempre es ordenado
	list<Componente*>::iterator it = componentes.begin();

	if (componentes.size() > 0) {
		while (it != componentes.end()) {
			DatoBSharp *dato =
					((DatoBSharp *) ((Registro*) (*it))->clonarDato());

			if (!((*dato->getClave()) < clave)) {
				delete dato;
				break;
			}

			delete dato;
			it++;
		}

		if (it != componentes.end()) {
			DatoBSharp *dato =
					((DatoBSharp *) ((Registro*) (*it))->clonarDato());

			if ((*dato ->getClave()) == clave) {
				delete dato;
				throw ClaveDuplicadaException();
			}

			delete dato;
		}
	}

	componentes.insert(it, componente);
}

bool BloqueBSharp::sePuedeBalancearEnDos(const BloqueBSharp &siblingDerecho) const {
	unsigned int tamanoDerecho = siblingDerecho.getTamanoSerializacion();
	unsigned int tamanoIzquierdo = this->getTamanoSerializacion();

	//TODO esto no es enteramente correcto (el igual no iría):
	if (tamanoDerecho == tamanoIzquierdo) {
		return false;
	}

	/* si ninguno de los dos, esta en overflow/underflow,
	 * el metodo fue llamado incorrectamente
	 */
	if (((!siblingDerecho.estaOverflow()) && (!siblingDerecho.estaUnderflow()))
			&& ((!this->estaOverflow()) && (!this->estaUnderflow()))) {
		throw NoSeDeberiaIntentarBalancearException();
	}

	if ((tamanoDerecho + tamanoIzquierdo) > 2 * (this->tamanoBloque)) {
		return false;
	}

	unsigned int componentesPromedio = ((tamanoDerecho + tamanoIzquierdo) / 2);
	unsigned long int tamanoMinimo = 2 * (this->tamanoBloque) / 3;

	if (tamanoIzquierdo > tamanoDerecho) {
		for (list<Componente*>::const_reverse_iterator it =
				this->componentes.rbegin(); it != this->componentes.rend(); it++) {
			if (!((tamanoIzquierdo - (*it)->getTamanoSerializacion()
					>= componentesPromedio) || (tamanoIzquierdo > tamanoBloque
					&& tamanoDerecho < tamanoBloque) || (((tamanoIzquierdo
					- (*it)->getTamanoSerializacion() >= tamanoMinimo)
					&& (tamanoDerecho < tamanoMinimo))))) {
				break;
			}

			tamanoDerecho += (*it)->getTamanoSerializacion();
			tamanoIzquierdo -= (*it)->getTamanoSerializacion();
		}
	} else if (tamanoIzquierdo < tamanoDerecho) {
		for (list<Componente*>::const_iterator it =
				siblingDerecho.componentes.begin(); ((it
				!= siblingDerecho.componentes.end()) && ((tamanoDerecho
				- (*it)->getTamanoSerializacion() >= componentesPromedio)
				|| (tamanoDerecho > tamanoBloque && tamanoIzquierdo
						< tamanoBloque) || ((tamanoDerecho
				- (*it)->getTamanoSerializacion() > tamanoMinimo)
				&& (tamanoIzquierdo < tamanoMinimo)))

		); it++) {
			tamanoIzquierdo += (*it)->getTamanoSerializacion();
			tamanoDerecho -= (*it)->getTamanoSerializacion();
		}
	}

	if ((tamanoDerecho > this->tamanoBloque) || (tamanoIzquierdo
			> this->tamanoBloque) || (tamanoDerecho < tamanoMinimo)
			|| (tamanoIzquierdo < tamanoMinimo)) {
		return false;
	}
	return true;
}

void BloqueBSharp::balancearEnDos(BloqueBSharp &siblingDerecho) {
	unsigned int componentesPromedio =
			((siblingDerecho.getTamanoSerializacion()
					+ this->getTamanoSerializacion()) / 2);

	bool respetarPromedio = true;

	if (this->getTamanoSerializacion()
			> siblingDerecho.getTamanoSerializacion()) {
		while ((this->getTamanoSerializacion() > componentesPromedio)
				|| (this->estaOverflow() && !siblingDerecho.estaOverflow())
				|| ((!this->estaUnderflow())
						&& (siblingDerecho.estaUnderflow()))) {
			respetarPromedio = !((this->estaOverflow()
					&& !siblingDerecho.estaOverflow())
					|| ((!this->estaUnderflow())
							&& (siblingDerecho.estaUnderflow())));

			Registro *aux = (Registro*) this->popBack();
			DatoBSharp *dato = ((DatoBSharp*) (aux)->clonarDato());
			siblingDerecho.agregar(aux, (*(dato->getClave())));
			delete dato;
		}

		if (respetarPromedio) {
			Registro *aux = (Registro*) siblingDerecho.popFront();
			DatoBSharp *dato = ((DatoBSharp*) (aux)->clonarDato());
			this->agregar(aux, (*(dato->getClave())));
			delete dato;
		}

	} else if (this->getTamanoSerializacion()
			< siblingDerecho.getTamanoSerializacion()) {
		while ((siblingDerecho.getTamanoSerializacion() > componentesPromedio)
				|| (siblingDerecho.estaOverflow() && !this->estaOverflow())
				|| ((!siblingDerecho.estaUnderflow())
						&& (this->estaUnderflow()))) {
			respetarPromedio = !((siblingDerecho.estaOverflow()
					&& !this->estaOverflow())
					|| ((!siblingDerecho.estaUnderflow())
							&& (this->estaUnderflow())));

			Registro *aux = (Registro*) siblingDerecho.popFront();
			DatoBSharp *dato = ((DatoBSharp*) (aux)->clonarDato());
			this->agregar(aux, (*(dato->getClave())));
			delete dato;
		}

		if (respetarPromedio) {
			Registro *aux = (Registro*) this->popBack();
			DatoBSharp *dato = ((DatoBSharp*) (aux)->clonarDato());
			siblingDerecho.agregar(aux, (*(dato->getClave())));
			delete dato;
		}
	}

	if (this->estaOverflow() || this->estaUnderflow()
			|| siblingDerecho.estaOverflow() || siblingDerecho.estaUnderflow()) {
		//TODO REALMENTE TIENE QUE HACERSE ESTE CONTROL?

		//throw ArbolInutilizableException();
	}

}

bool BloqueBSharp::sePuedeBalancearEnTres(const BloqueBSharp &nuevoNodo,
		const BloqueBSharp &siblingDerecho) const {
	unsigned long int tamanoTotal = this->getTamanoSerializacion()
			+ nuevoNodo.getTamanoSerializacion()
			+ siblingDerecho.getTamanoSerializacion();

	list<Componente*> listaComponentes(this->componentes);

	listaComponentes.insert(listaComponentes.end(),
			siblingDerecho.componentes.begin(),
			siblingDerecho.componentes.end());

	unsigned long int tamanoBloqueInicial = nuevoNodo.getTamanoSerializacion();

	unsigned long int tamanoBloqueIzquierdo = tamanoBloqueInicial;
	unsigned long int tamanoBloqueCentral = tamanoBloqueInicial;
	unsigned long int tamanoBloqueDerecho = tamanoBloqueInicial;

	while ((tamanoBloqueIzquierdo < (tamanoTotal / 3))
			&& (listaComponentes.size() != 0)) {
		tamanoBloqueIzquierdo
				+= listaComponentes.front()->getTamanoSerializacion();
		listaComponentes.pop_front();
	}

	while ((tamanoBloqueCentral < (tamanoTotal / 3))
			&& (listaComponentes.size() != 0)) {
		tamanoBloqueCentral
				+= listaComponentes.front()->getTamanoSerializacion();
		listaComponentes.pop_front();
	}

	while (listaComponentes.size() != 0) {
		tamanoBloqueDerecho
				+= listaComponentes.front()->getTamanoSerializacion();
		listaComponentes.pop_front();
	}

	return (tamanoBloqueDerecho < ((float(2 * tamanoBloque)) / float(3)));
}

void BloqueBSharp::balancearEnTres(BloqueBSharp &nuevoNodo,
		BloqueBSharp &siblingDerecho) {

	unsigned long int tamanoTotal = this->getTamanoSerializacion()
			+ nuevoNodo.getTamanoSerializacion()
			+ siblingDerecho.getTamanoSerializacion();

	list<Componente*> listaComponentes(this->componentes);
	this->componentes.clear();

	listaComponentes.insert(listaComponentes.end(),
			siblingDerecho.componentes.begin(),
			siblingDerecho.componentes.end());
	siblingDerecho.componentes.clear();

	while ((this->getTamanoSerializacion() < (tamanoTotal / 3))
			&& (listaComponentes.size() != 0)) {
		this->componentes.push_back(listaComponentes.front());
		listaComponentes.pop_front();
	}

	while ((nuevoNodo.getTamanoSerializacion() < (tamanoTotal / 3))
			&& (listaComponentes.size() != 0)) {
		nuevoNodo.componentes.push_back(listaComponentes.front());
		listaComponentes.pop_front();
	}

	while (listaComponentes.size() != 0) {
		siblingDerecho.componentes.push_back(listaComponentes.front());
		listaComponentes.pop_front();
	}
}

bool BloqueBSharp::sePuedeUnirTresEnDos(const BloqueBSharp &nodoAVaciar,
		const BloqueBSharp &siblingDerecho) const {
	list<Componente*>::const_iterator it = nodoAVaciar.componentes.begin();

	unsigned long int tamanoIzquierdo = this->getTamanoSerializacion();
	unsigned long int tamanoDerecho = siblingDerecho.getTamanoSerializacion();

	while (it != nodoAVaciar.componentes.end()) {
		if ((tamanoIzquierdo + (*it)->getTamanoSerializacion()) > tamanoBloque) {
			break;
		}

		tamanoIzquierdo += (*it)->getTamanoSerializacion();

		it++;
	}

	while (it != nodoAVaciar.componentes.end()) {
		tamanoDerecho += (*it)->getTamanoSerializacion();

		it++;
	}

	return ((tamanoIzquierdo <= tamanoBloque)
			&& (tamanoDerecho <= tamanoBloque));
}

void BloqueBSharp::unirTresEnDos(BloqueBSharp &nodoAVaciar,
		BloqueBSharp &siblingDerecho) {
	while (nodoAVaciar.cantElementos() > 0) {
		Registro *aux = (Registro*) nodoAVaciar.popFront();

		DatoBSharp *dato = ((DatoBSharp*) (aux)->clonarDato());

		this->agregar(aux, (*(dato->getClave())));

		delete dato;
	}

	balancearEnDos(siblingDerecho);

}

bool BloqueBSharp::estaUnderflow() const {
	return (this->getTamanoSerializacion() < ((float(2 * tamanoBloque))
			/ float(3)));
}

bool BloqueBSharp::estaOverflow() const {
	return (this->espacioLibre() < 0);
}

bool BloqueBSharp::estaOverflowRaiz() const {
	return ((float(this->getTamanoSerializacion())
			/ float(this->getTamanoBloque())) > (float(4) / float(3)));
}

bool BloqueBSharp::esHoja() const {
	return nivelNodo == 0;
}

unsigned long int BloqueBSharp::nodoSiguiente(const Clave &clave) const {
	if (esHoja()) {
		return direccion;
	} else {
		list<Componente*>::const_reverse_iterator it = componentes.rbegin();

		if (!componentes.empty()) {
			DatoBSharp *dato =
					((DatoBSharp *) ((Registro*) (*it))->clonarDato());
			if ((*dato->getClave()) < clave) {
				unsigned long int dir = dato->getPosicion();
				delete dato;
				return dir;
			}
			delete dato;
		}

		while (it != componentes.rend()) {
			DatoBSharp *dato =
					((DatoBSharp *) ((Registro*) (*it))->clonarDato());

			if ((*dato->getClave()) == clave) {
				unsigned long int dir = dato->getPosicion();
				delete dato;
				return dir;

			} else if ((*dato->getClave()) < clave) {
				it--;
				delete dato;
				dato = ((DatoBSharp *) ((Registro*) (*it))->clonarDato());
				unsigned long int dir = dato->getPosicion();
				delete dato;
				return dir;
			}

			it++;

			delete dato;
		}

		if (!componentes.empty()) {
			DatoBSharp
					*dato =
							(DatoBSharp *) (((Registro*) componentes.front())->clonarDato());
			unsigned long int dir = dato->getPosicion();
			delete dato;
			return dir;
		} else {
			return direccion;
		}
	}
}

string BloqueBSharp::especializarSerializacion() const {
	stringstream ss;

	serializacionDigito(ss, tSerializacion, direccion);
	serializacionDigito(ss, tSerializacion, nivelNodo);

	return ss.str();

}

void BloqueBSharp::especializarHidratacion(stringstream &serializacion) {
	hidratacionDigito(serializacion, tSerializacion, direccion);
	hidratacionDigito(serializacion, tSerializacion, nivelNodo);
}

unsigned long int BloqueBSharp::getDireccion() const {
	return direccion;
}

void BloqueBSharp::setDireccion(const unsigned long int &direccion) {
	this->direccion = direccion;
}

Clave* BloqueBSharp::claveMaxima() const {
	Clave *clave = NULL;
	if (!componentes.empty()) {
		DatoBSharp
				*datoB =
						(DatoBSharp*) ((Registro*) this->componentes.back())->clonarDato();

		clave = datoB->getClave()->clonar();

		delete datoB;
	}

	return clave;
}

Clave* BloqueBSharp::claveMinima() const {
	Clave *clave = NULL;
	if (!componentes.empty()) {
		DatoBSharp
				*datoB =
						(DatoBSharp*) ((Registro*) this->componentes.front())->clonarDato();

		clave = datoB->getClave()->clonar();

		delete datoB;
	}

	return clave;
}

BloqueBSharp* BloqueBSharp::partirRaiz() {
	BloqueBSharp *bloqueBSharp = new BloqueBSharp(tamanoBloque, tSerializacion);

	while ((bloqueBSharp->getTamanoSerializacion()
			< this->getTamanoSerializacion() && (!this->estaUnderflow()))) {
		Registro *registro = (Registro*) this->popBack();
		DatoBSharp *dato = (DatoBSharp*) registro->clonarDato();
		Clave *clave = dato->getClave();
		bloqueBSharp->agregar(registro, *clave);

		delete dato;
	}

	if (this->estaUnderflow() && (bloqueBSharp->cantElementos() > 0)) {
		Registro *registro = (Registro*) bloqueBSharp->popFront();
		DatoBSharp *dato = (DatoBSharp*) registro->clonarDato();
		Clave *clave = dato->getClave();
		this->agregar(registro, *clave);

		delete dato;
	}

	return bloqueBSharp;
}

void BloqueBSharp::unirRaiz(BloqueBSharp &bloqueBSharp) {
	while (bloqueBSharp.cantElementos() > 0) {
		Registro *registro = (Registro*) bloqueBSharp.popBack();
		DatoBSharp *datoBSharp = (DatoBSharp*) registro->clonarDato();
		Clave *clave = datoBSharp->getClave();
		this->agregar(registro, *clave);

		delete datoBSharp;
	}

}

long int BloqueBSharp::siblingDerecho(const Clave &clave) const {
	if (componentes.empty()) {
		return -1;
	}
	list<Componente*>::const_reverse_iterator it = componentes.rbegin();
	it++;

	while (it != componentes.rend()) {
		DatoBSharp
				*dato =
						dynamic_cast<DatoBSharp *> (dynamic_cast<Registro *> ((*it))-> clonarDato());
		if (clave == (*dato->getClave())) {
			it--;
			delete dato;
			dato
					= dynamic_cast<DatoBSharp *> (dynamic_cast<Registro *> ((*it))-> clonarDato());
			long int resultado = dato->getPosicion();
			delete dato;
			return resultado;
		}

		it++;
	}

	return -1;
}

long int BloqueBSharp::siblingIzquierdo(const Clave &clave) const {
	if (componentes.empty()) {
		return -1;
	}
	list<Componente*>::const_iterator it = componentes.begin();
	it++;

	while (it != componentes.end()) {
		DatoBSharp
				*dato =
						dynamic_cast<DatoBSharp *> (dynamic_cast<Registro *> ((*it))-> clonarDato());
		if (clave == (*dato->getClave())) {
			it--;
			delete dato;
			dato
					= dynamic_cast<DatoBSharp *> (dynamic_cast<Registro *> ((*it))-> clonarDato());
			long int resultado = dato->getPosicion();
			delete dato;
			return resultado;
		}

		it++;
	}

	return -1;

}

bool BloqueBSharp::sePuedeUnirRaiz(const BloqueBSharp &bloqueBSharp) const {
	unsigned long int tamanoIzquierdo = this->getTamanoSerializacion();

	list<Componente*>::const_iterator it = bloqueBSharp.componentes.begin();
	while (it != bloqueBSharp.componentes.end()) {
		Registro *registro = dynamic_cast<Registro *> (*it);

		tamanoIzquierdo += registro->getTamanoSerializacion();

		it++;
	}

	return (tamanoIzquierdo < (4 * getTamanoBloque() / 3));

}

list<unsigned long int> BloqueBSharp::imprimirYPoisciones() const {

	cout << "apunta: " << this->direccion << ", nivel: " << this->nivelNodo
			<< ", cant: " << this->componentes.size() << ";\t";

	list<unsigned long int> listaDirecciones;

	for (list<Componente*>::const_iterator it = componentes.begin(); it
			!= componentes.end(); it++) {
		DatoBSharp *dato = (DatoBSharp*) ((Registro*) (*it))->clonarDato();

		unsigned long int posicion = dato->getPosicion();
		listaDirecciones.push_back(posicion);

		stringstream serializacionClave;
		if (this->tSerializacion == TEXTO) {
			dato->getClave()->serializar(serializacionClave);

		}

		cout << "(" << posicion << ") " << serializacionClave.str() << " ";

		delete dato;
	}
	cout << endl;
	return listaDirecciones;
}

Componente *BloqueBSharp::clonar() const {
	BloqueBSharp *nuevo = new BloqueBSharp(tamanoBloque, tSerializacion);

	nuevo->setDireccion(this->getDireccion());
	nuevo->setNivelNodo(this->getNivelNodo());
	for (list<Componente*>::const_iterator it = componentes.begin(); it
			!= componentes.end(); it++) {
		nuevo->componentes.push_back((*it)->clonar());
	}

	return nuevo;
}

bool BloqueBSharp::getClaveSiguiente(const Clave &clave, Clave*& claveSiguiente) {

	for (list<Componente*>::const_iterator it = componentes.begin(); it != componentes.end(); it++) {
		DatoBSharp* datoBSharp = (DatoBSharp*) ((Registro*)(*it))->clonarDato();

		if ((*datoBSharp->getClave()) == clave) {
			delete datoBSharp;
			it++;
			datoBSharp = (DatoBSharp*) ((Registro*)(*it))->clonarDato();
			claveSiguiente = datoBSharp->getClave()->clonar();
			delete datoBSharp;
			return true;
		} else {
			delete datoBSharp;
		}
	}
	return false;
}

}
